class Solution {
    int n = 0;
    int[] memo;
    public int lengthOfLIS(int[] nums) {
        n = nums.length;
        memo = new int[n];
        int max = 0;
        for(int i = 0; i < n; i++){
            int tmp = dfs(nums, i);
            max = Math.max(max, tmp);
        }
        return max;
    }
    public int dfs(int[] nums, int pos){
        if(memo[pos] != 0){
            return memo[pos];
        }
        int max = 1;
        for(int i = pos + 1; i < n; i++){
            int tmp = 0;
            if(nums[pos] < nums[i]){
                tmp = dfs(nums, i) + 1;
            }
            max = Math.max(max, tmp);
        }
        memo[pos] = max;
        return max;
    }
}